/**
给定字符串 s，将 s 划分成子串，使得每个子串为回文子串，求最小划分次数。例如，输
入 s=“aab”，返回 1，因为 s 可以经 1 次划分，成为 “aa”,“b” 两个回文子串。
*/

#include <stdio.h>
#include <string>

using namespace std;

bool isPalindrome(string s, int i,int j){
    while(i<j){
        if(s[i]!=s[j]){
            return false;
        }
        ++i;
        --j;
    }
    return true;
}

int minCut(string s){
    int totalLength = s.length();
    int *M = new int[totalLength];
    M[0]=0;
    for(int i=1;i<totalLength;++i){
        int min = totalLength;
        for(int j=0;j<=i;++j){
            int cut = totalLength;
            if(isPalindrome(s,j,i)){
                if(j>0){
                    cut = M[j-1]+1;
                }
                else{
                    cut = 0;
                }
                if(min>cut){
                    min = cut;
                }
            }
        }
        M[i]=min;
    }
    return M[totalLength-1];
}

int main(){
    string s = "aaaaaaaaaaaaabaaaaaa";
    printf("minCut:%d", minCut(s));
}
